package com.sunny.l34;

import java.util.concurrent.LinkedBlockingQueue;

public class Solution {
    public void connect(TreeLinkNode root) {
        if(null == root)
            return;
        LinkedBlockingQueue<TreeLinkNode> queue1 = new LinkedBlockingQueue<>();
        LinkedBlockingQueue<TreeLinkNode> queue2 = new LinkedBlockingQueue<>();

        queue1.offer(root);
        int size1 = 1;
        int size2 = 0;
        int tag = 1;
        TreeLinkNode prev = null;
        while ((1==tag && !queue1.isEmpty()) || (2==tag && !queue2.isEmpty())){
            if(1==tag){
                TreeLinkNode tmp = queue1.poll();
                if(null != prev){
                    prev.next = tmp;
                }
                if(null != tmp.left){
                    queue2.offer(tmp.left);
                    size2++;
                }
                if(null != tmp.right){
                    queue2.offer(tmp.right);
                    size2++;
                }
                prev = tmp;
                size1--;
                if(0 == size1){
                    tmp.next = null;
                    tag = 2;
                    prev = null;
                }
            }else{
                TreeLinkNode tmp = queue2.poll();
                if(null != prev){
                    prev.next = tmp;
                }
                if(null != tmp.left){
                    queue1.offer(tmp.left);
                    size1++;
                }
                if(null != tmp.right){
                    queue1.offer(tmp.right);
                    size1++;
                }
                prev = tmp;
                size2--;
                if(0 == size2){
                    tmp.next = null;
                    tag = 1;
                    prev = null;
                }
            }
        }

    }
}

class TreeLinkNode {
    int val;
    TreeLinkNode left, right, next;
    TreeLinkNode(int x) { val = x; }
}
